1. Field of the Invention
The present invention relates to a public key generation method in Elliptic Curve Cryptography (ECC), and a public key generation system performing the method. More particularly, the present invention relates to a public key generation method which can quickly compute a public key using an elliptic curve over finite fields of characteristic three.
2. Description of Related Art
Public key cryptography, introduced by W. Diffei and M. Hellman in 1976, is an asymmetrical method using different keys during encryption and decryption. The public key encryption uses two keys, a public key and a private key. The public key is used for encrypting a message, and the private key being used for decrypting a ciphertext into the original message.
The RSA algorithm and the Merkle-Hellman algorithm, are presently endorsed in terms of security as the public key encryption method.
Elliptic curve cryptography is an approach to public key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves cryptography was proposed by Neal Koblitz and Victor Miller in 1985. The discrete logarithm problem on the elliptic curve is believed to be more difficult than the corresponding problem in the multiplicative group of nonzero elements of the underlying finite field. Thus, the keys chosen in elliptic curve cryptography can be much shorter for a comparable level of security.
For example, the RSA algorithm requires a 1024 bit key and an ECC algorithm requires a 160 bit key for a comparable level of security. Accordingly, the usage of elliptic curve cryptography can improve the performance of the existing solutions for the wireless Internet and IC cards.
FIG. 1 illustrates an example of a conventional public key cryptography method based on ECC.
Two user terminals 101 and 102 respectively include private keys 103 and 104, and include a common generator P (not illustrated). In this case, the first user terminal 101 may generate a public key aP 105 using the common generator P and the first user terminal's 101 own private key 103, and the second user terminal 102 may generate a public key bP 106 using the common generator P and the second user terminal's 102 own private key 104.
The user terminals 101 and 102 exchange the generated public keys aP 105 and bP 106 with each other to generate common encryption keys a(bP) 107 and b(aP) 108. In other words, the user terminals 101 and 102 have a common key abP to share.
However, the conventional art fails to take full advantage of the improved performance capabilities of keys in elliptic curve cryptography while maintaining a comparable level of security.
Accordingly, there is a need for an improved public key generation method wherein a public key may be quickly computed by reducing a sequence length of a private key represented in signed ternary τ-adic expansion and optimizing the public key by applying a splitting algorithm to a public key whose sequence is reduced.